package com.xigua._递归;

/**
 * @author LiRongHua
 * @Title: ${file_name}
 * @Package ${package_name}
 * @Description: 给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。
 * 数组中的每个元素代表你在该位置可以跳跃的最大长度。
 *
 *判断你是否能够到达最后一个下标。
 *
 *
 * @date 2022/3/2620:33
 */
public class _55_跳跃游戏 {

    public boolean canJump(int[] nums) {
        int length = nums.length;
        if (length == 1) return true;
        int minStep = 1;        //定义一个数，为达到最后最后一个结点最小需要的步数
        for (int i = length-2; i >0; i--) {          //从倒数第二个往第二个开始遍历
            if (nums[i]<minStep){            // 如果当前元素的值小于最小步数,则到达最后一个元素的最小步数+1;
                minStep++;
            }else {
                minStep = 1;              //如果当前元素的值大于或等于最小步数，则一定能到达最后一个元素，
                                    // 此时可以就当前元素认为是最后一个元素，并对于前一个元素来说最小步数为1;
            }
        }

        return nums[0] >= minStep;       //此时minStep为达到"最后一个元素"(并不是nums[length-1])的最小步数，只要判断第一个元素的值是否大于或等于最小步数就可以了;
    }
}

